package main

import (
	"fmt"
)

// 小孩的结构体
type Boy struct {
	No int // 编号
	Next *Boy // 指向下一个小孩的指针[默认值是nil]
}

// 编写一个函数，构成单向环形链表
// num : 表示小孩的个数
// *Boy : 返回该环形的链表的第一个指针
func AddBoy(num int) *Boy {

	first := &Boy{} // 空节点
	curBoy := &Boy{}

	// 判断
	if num < 1 {
		fmt.Println("num的值不对")
		return first
	} 

	// 循环构建环形链表
	for i := 1; i <= num; i++ {
		boy := &Boy {
			No : i,
		}
		if i == 1 {
			first = boy
			curBoy = boy
			curBoy.Next = first // 形成循环
		} else {
			curBoy.Next = boy
			curBoy = boy
			curBoy.Next = first // 构成环形链表
		}
	}
	return first
}

// 显示单向的环形链表
func ShowBoy(first *Boy) {

	// 处理环形链表为空
	if first.Next == nil {
		fmt.Println("链表为空，没有小孩")
		return
	}

	// 创建一个指针，帮助遍历
	curBoy := first
	for {
		fmt.Printf("%d -> ", curBoy.No)
		if curBoy.Next == first {
			break
		}
		curBoy = curBoy.Next
	}
	fmt.Println()
}

func PlayGame(first *Boy, startNo int, countNum int) {

	// 1. 空的链表单独处理
	if first.Next == nil {
		fmt.Println("空的链表，没有小孩")
		return
	}

	// 2. 定义辅助指针，帮助我们删除小孩
	tail := first

	// 3. 让tail执行环形链表的最后一个小孩
	for {
		if tail.Next == first {
			break
		}
		tail = tail.Next
	}

	// 4. 让first移动到startNo，[后面我们删除小孩，就以first为准]
	for i := 1; i <= startNo - 1; i++ {
		first = first.Next
		tail = tail.Next
	}

	// 5. 开始数 countNum下，然后就删除first指向的小孩
	for {
		// 开始数countNum - 1次
		for i := 1; i <= countNum - 1; i++ {
			first = first.Next
			tail = tail.Next
		}
		fmt.Printf("小孩编号为%d 出圈 ->\n", first.No)
		// 删除first执行的小孩
		first = first.Next
		tail.Next = first
		// 判断如果 tail == first，圈子中只有一个小孩，我们就留下
		if tail == first {
			break
		}
	}
	fmt.Printf("最后出圈的小孩编号%d 出圈 ->", first.No)
}

func main() {

	first := AddBoy(10)
	ShowBoy(first)
	PlayGame(first, 2, 3)

}